package com.yuufa.test.ex;

public class Ex4 {

    static int n = 5;
    static int max = 8;

    public static void main(String[] args) {
        Fruit[] f = {new Fruit("李子", 4, 4500), new Fruit("蘋果", 5, 5700), 
                     new Fruit("橘子", 2, 2250),
                     new Fruit("草莓", 1, 1100), new Fruit("甜瓜", 6, 6700)};
        int[] value = {0, 0, 0, 0, 0, 0, 0, 0, 0};
        Fruit[] order = {null, null, null, null, null, null, null, null, null};
        
        for (int i = 0; i < f.length; i++) {
            Fruit fruit = f[i];
            
            int weight = fruit.getWeight();
            int price = fruit.getPrice();
            
            for (int j = weight; j <= max; j++) {
                if( value[j] < (price + value[j-weight]) ) {
                    value[j] = price + value[j-weight];
                    order[j] = fruit;
                }
            }
        }
        
        for(int k=1;k<=max;k++) {
            String name = print(order, k);
            System.out.print(String.format("背包重量:%2d,最大價格:%4d,%s\n", k, value[k], name));
        }
    }
    
    public static String print(Fruit[] order, int w) {
        String name = "";
        
        while(w != 0) {
            Fruit f = order[w];
            w = w - f.getWeight();
            
            name += f.getName() + ",";
        }
        
        return name;
    }

}

class Fruit {

    private String name;
    private Integer weight;
    private Integer price;

    public Fruit(String name, Integer weight, Integer price) {
        this.name = name;
        this.weight = weight;
        this.price = price;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Integer getWeight() {
        return weight;
    }

    public void setWeight(Integer weight) {
        this.weight = weight;
    }

    public Integer getPrice() {
        return price;
    }

    public void setPrice(Integer price) {
        this.price = price;
    }

}